DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2018.64

Probabilistic Secret Sharing

Authors: Paolo D'Arco, Roberto De Prisco, Alfredo De Santis, Angel Pérez del Pozo, and Ugo Vaccaro

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract

In classical secret sharing schemes a dealer shares a secret among a set of participants in such a way that qualified subsets can reconstruct the secret, while forbidden ones do not get any kind of information about it. The basic parameter to optimize is the size of the shares, that is, the amount of secret information that the dealer has to give to participants. In this paper we formalize a notion of probabilistic secret sharing schemes, in which qualified subsets can reconstruct the secret but only with a certain controlled probability. We show that, by allowing a bounded error in the reconstruction of the secret, it is possible to drastically reduce the size of the shares the participants get (with respect to classical secret sharing schemes). We provide efficient constructions both for threshold access structures on a finite set of participants and for evolving threshold access structures, where the set of participants is potentially infinite. Some of our constructions yield shares of constant size (i.e., not depending on the number of participants) and an error probability of successfully reconstructing the secret which can be made as close to 1 as desired.

Cite as

Paolo D'Arco, Roberto De Prisco, Alfredo De Santis, Angel Pérez del Pozo, and Ugo Vaccaro. Probabilistic Secret Sharing. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 64:1-64:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{darco_et_al:LIPIcs.MFCS.2018.64,
  author =	{D'Arco, Paolo and De Prisco, Roberto and De Santis, Alfredo and P\'{e}rez del Pozo, Angel and Vaccaro, Ugo},
  title =	{{Probabilistic Secret Sharing}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{64:1--64:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.64},
  URN =		{urn:nbn:de:0030-drops-96464},
  doi =		{10.4230/LIPIcs.MFCS.2018.64},
  annote =	{Keywords: Secret sharing, probabilistic secret sharing, evolving secret sharing}
}

Document

DOI: 10.4230/DagSemProc.09281.1

09281 Abstracts Collection – Search Methodologies

Authors: Rudolf Ahlswede, Ferdinando Cicalese, and Ugo Vaccaro

Published in: Dagstuhl Seminar Proceedings, Volume 9281, Search Methodologies (2009)

Abstract

From 05.07.09 to 10.07.09, the Dagstuhl Seminar 09281 on ``Search Methodologies '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. Abstracts of the presentations given during the seminar are put together in this paper. The first section describes the seminar topics and goals in general. We also briefly comment on how the topics were addressed in the talks. Links to extended abstracts or full papers are provided, if available.

Cite as

Rudolf Ahlswede, Ferdinando Cicalese, and Ugo Vaccaro. 09281 Abstracts Collection – Search Methodologies. In Search Methodologies. Dagstuhl Seminar Proceedings, Volume 9281, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{ahlswede_et_al:DagSemProc.09281.1,
  author =	{Ahlswede, Rudolf and Cicalese, Ferdinando and Vaccaro, Ugo},
  title =	{{09281 Abstracts Collection – Search Methodologies}},
  booktitle =	{Search Methodologies},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9281},
  editor =	{Rudolf Ahlswede and Ferdinando Cicalese and Ugo Vaccaro},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09281.1},
  URN =		{urn:nbn:de:0030-drops-22457},
  doi =		{10.4230/DagSemProc.09281.1},
  annote =	{Keywords: Search algorithms, group testing, fault-tolerance, identification, decision tree, multi-access communication}
}

Search Results

Documents authored by Vaccaro, Ugo

Probabilistic Secret Sharing

Abstract

Cite as

09281 Abstracts Collection – Search Methodologies

Abstract

Cite as

Thanks for your feedback!

Could not send message